package io.zouyalong.algo.leetcode;

import java.util.HashMap;
import java.util.Stack;

/**
 *
 */
public class LongestValidParentheses {
    public static void main(String[] args) {
        var src = "(((()())";
        var inst = new LongestValidParentheses();
        System.out.printf("Max length: %d\n", inst.solution1Dp(src));
    }

    class Bracket {
        int pos;
        char c;

        public Bracket(char c, int pos) {
            this.c = c;
            this.pos = pos;
        }
    }

    public int solution1Dp(String src) {
        if (src.length() == 0) {
            return 0;
        }
        var chars = src.toCharArray();
        var stack = new Stack<Bracket>();
        // 存储合格的括号组，key 为右括号的 index，值为该对称组的长度
        var validRightLen = new HashMap<Integer, Integer>();
        int longest = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ')') {
                if (stack.empty()) {
                    // 多余的右括号
                    continue;
                }
                var left = stack.pop();
                var currentLen = i - left.pos + 1;
                if (left.pos > 0) {
                    currentLen += validRightLen.getOrDefault(left.pos - 1, 0);
                }
                if (currentLen > longest) {
                    longest = currentLen;
                }
                validRightLen.put(i, currentLen);
            } else {
                // (
                stack.push(new Bracket(chars[i], i));
            }
        }
        return longest;
    }
}
